class MergeSort {
    constructor() {
        this.data = [];
    }

    sort(data) {
        this.data = [...data];
        this.dfs(0, this.data.length - 1);
        Object.assign(data, this.data);
    }

    dfs(start, end) {
        if (start === end) {
            return;
        }

        const mid = Math.floor((start + end) / 2);
        this.dfs(start, mid);
        this.dfs(mid + 1, end);
        this.merge(start, mid, end);
    }

    merge(start, mid, end) {
        let i = start, j = mid + 1;
        const temp = [];
        while (i <= mid && j <= end) {
              if (this.data[i] < this.data[j]) {
                  temp.push(this.data[i++]);
              } else {
                  temp.push(this.data[j++]);
              }
         }
         while (i <= mid) {
             temp.push(this.data[i++]);
         }
         while (j <= end) {
             temp.push(this.data[j++]);
         }
         for (let k = start, t = 0; k <= end; k++, t++) {
             this.data[k] = temp[t];
         }
     }
}